// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents.  Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
//
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to write it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
//     so do not keep them longer than necessary.


#include "types.h"
#include "param.h"
#include "spinlock.h"
#include "sleeplock.h"
#include "riscv.h"
#include "defs.h"
#include "fs.h"
#include "buf.h"

/*struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // Sorted by how recently the buffer was used.
  // head.next is most recent, head.prev is least.
  struct buf head;
} bcache;*/

//改成23或29的话，bget里的家贼就可以不用当了，但似乎两种方法都不能从根源解决死锁的可能性，具体死锁原因在bget里有注释
#define NBUCKETS 13

struct {
  struct spinlock lock[NBUCKETS];
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // head.next is most recently used.
  //struct buf head;
  struct buf hashbucket[NBUCKETS]; // 每个哈希队列一个linked list及一个lock
} bcache;

void
binit(void)
{
  struct buf *b;

  //初始化，桶子内没东西~
  for(int i = 0 ; i < NBUCKETS ; i++)
  {
    initlock(&bcache.lock[i], "bcache");
    bcache.hashbucket[i].prev = &bcache.hashbucket[i];
    bcache.hashbucket[i].next = &bcache.hashbucket[i];
  }

  //进桶子去吧！
  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
    int hash = b->blockno % NBUCKETS;
    b->next = bcache.hashbucket[hash].next;
    b->prev = &bcache.hashbucket[hash];
    initsleeplock(&b->lock, "buffer");
    bcache.hashbucket[hash].next->prev = b;
    bcache.hashbucket[hash].next = b;
  }
}

// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint blockno)
{
  /* 
  报错panic: sched locks说有锁没解开
  怎么想都是这块问题
  逻辑上应该是
  a进程进来找0桶没有然后去找1桶
  b进程进来找1桶没有然后去找0桶
  然后就死锁了QAQ
  
  看知乎说可以找不到先偷自己的来解决问题
  （好像不能从根源解决啊kuso）
  实验指导书说可以尝试更改桶子的大小
  */
  struct buf *b;
  // 引入hash，操作改为对桶子操作即可
  int hash = blockno % NBUCKETS;

  acquire(&bcache.lock[hash]);

  // Is the block already cached?
  for(b = bcache.hashbucket[hash].next; b != &bcache.hashbucket[hash]; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      b->refcnt++;
      release(&bcache.lock[hash]);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // 进行一个家贼的当，如果改了桶的大小就可以考虑把这个for循环去掉
  for(b = bcache.hashbucket[hash].next; b != &bcache.hashbucket[hash]; b = b->next){
    // 把下面逻辑拿上来就行
    if(b->refcnt == 0) {
        b->dev = dev;
        b->blockno = blockno;
        b->valid = 0;
        b->refcnt = 1;
        release(&bcache.lock[hash]);
        acquiresleep(&b->lock);
        return b;
    }
  }

  // Not cached.
  // Recycle the least recently used (LRU) unused buffer.
  // 没命中，那就，偷，就硬偷 ~
  for(int i = 0 ; i < NBUCKETS ; i++)
  {
    // 跟前面一样又是熟悉的锁自己两次会报错，需要跳过
    if(i == hash) continue;
    // 上锁
    acquire(&bcache.lock[i]);
    for(b = bcache.hashbucket[i].prev; b != &bcache.hashbucket[i]; b = b->prev){
      if(b->refcnt == 0) {
        b->dev = dev;
        b->blockno = blockno;
        b->valid = 0;
        b->refcnt = 1;
        // 把b从原来的断开偷走~
        b->next->prev = b->prev;
        b->prev->next = b->next;
        // 装b（谐音梗扣钱）
        b->next = bcache.hashbucket[hash].next;
        b->prev = &bcache.hashbucket[hash];
        bcache.hashbucket[hash].next->prev = b;
        bcache.hashbucket[hash].next = b;
        //记得解锁
        release(&bcache.lock[i]);
        // 差点忘了前面锁的还没解。。。这里是直接返回的
        release(&bcache.lock[hash]);
        acquiresleep(&b->lock);
        return b;
      }
    }
    // 记得解锁
    release(&bcache.lock[i]);
  }
  release(&bcache.lock[hash]);
  panic("bget: no buffers");
}

// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;

  b = bget(dev, blockno);
  if(!b->valid) {
    virtio_disk_rw(b, 0);
    b->valid = 1;
  }
  return b;
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  virtio_disk_rw(b, 1);
}

// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  // 改为哈希桶操作
  int hash = b->blockno % NBUCKETS;
  acquire(&bcache.lock[hash]);
  b->refcnt--;
  if (b->refcnt == 0) {
    // no one is waiting for it.
    b->next->prev = b->prev;
    b->prev->next = b->next;
    b->next = bcache.hashbucket[hash].next;
    b->prev = &bcache.hashbucket[hash];
    bcache.hashbucket[hash].next->prev = b;
    bcache.hashbucket[hash].next = b;
  }
  
  release(&bcache.lock[hash]);
}

void
bpin(struct buf *b) {
  // 改为哈希桶操作
  int hash = b->blockno % NBUCKETS;
  acquire(&bcache.lock[hash]);
  b->refcnt++;
  release(&bcache.lock[hash]);
}

void
bunpin(struct buf *b) {
  // 同上。。。
  int hash = b->blockno % NBUCKETS;
  acquire(&bcache.lock[hash]);
  b->refcnt--;
  release(&bcache.lock[hash]);
}